package pers.tz.题目.leetcode.链表;

import pers.tz.common.ListNode;
import pers.tz.common.ListUtils;

/**
 * @author irony
 * @date 2024-03-16
 */
public class leetcode_0148_排序链表 {
//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
// 示例 1：
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//
// 示例 2：
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//
// 示例 3：
//输入：head = []
//输出：[]
//
// 提示：
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内
// -10⁵ <= Node.val <= 10⁵
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
    public static void main(String[] args) {
        ListNode listNode = ListUtils.generateList(10, 1, 15);
        ListUtils.printList(listNode);

        ListUtils.printList(sortList(listNode));
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = getMid(head);
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        return merge(left, right);
    }

    // 找到链表的中间节点，并断开链表
    private static ListNode getMid(ListNode head) {
        ListNode s = head;
        ListNode f = head;
        ListNode prev = null;

        while (f != null && f.next != null) {
            prev = s;
            s = s.next;
            f = f.next.next;
        }

        if (prev != null) {
            prev.next = null;
        }

        return s;
    }

    private static ListNode merge(ListNode left, ListNode right) {
        if (left == null || right == null) {
            return left == null ? right : left;
        }

        // 锁死头节点
        ListNode head = left.val < right.val ? left : right;

        // 三个指针，两个分别指向各自链表的比较节点，一个指向决定节点，决定下个节点指向哪里
        ListNode compareCur1 = head.next;
        ListNode compareCur2 = left.val < right.val ? right : left;
        ListNode modifyCur = head;

        while (compareCur1 != null && compareCur2 != null) {
            if (compareCur1.val <= compareCur2.val) {
                modifyCur.next = compareCur1;
                compareCur1 = compareCur1.next;
            } else {
                modifyCur.next = compareCur2;
                compareCur2 = compareCur2.next;
            }
            modifyCur = modifyCur.next;
        }

        modifyCur.next = compareCur1 != null ? compareCur1 : compareCur2;
        return head;
    }
}
